{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Count of Positive Integer and Negative Integer"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search #counting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找 #计数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maximumCount"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #正整数和负整数的最大计数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个按 <strong>非递减顺序</strong> 排列的数组 <code>nums</code> ，返回正整数数目和负整数数目中的最大值。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>换句话讲，如果 <code>nums</code> 中正整数的数目是 <code>pos</code> ，而负整数的数目是 <code>neg</code> ，返回 <code>pos</code> 和 <code>neg</code>二者中的最大值。</li>\n",
    "</ul>\n",
    "\n",
    "<p><strong>注意：</strong><code>0</code> 既不是正整数也不是负整数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [-2,-1,-1,1,2,3]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>共有 3 个正整数和 3 个负整数。计数得到的最大值是 3 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [-3,-2,-1,0,0,1,2]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>共有 2 个正整数和 3 个负整数。计数得到的最大值是 3 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [5,20,66,1314]\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>共有 4 个正整数和 0 个负整数。计数得到的最大值是 4 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 2000</code></li>\n",
    "\t<li><code>-2000 &lt;= nums[i] &lt;= 2000</code></li>\n",
    "\t<li><code>nums</code> 按 <strong>非递减顺序</strong> 排列。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶：</strong>你可以设计并实现时间复杂度为 <code>O(log(n))</code> 的算法解决此问题吗？</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-count-of-positive-integer-and-negative-integer](https://leetcode.cn/problems/maximum-count-of-positive-integer-and-negative-integer/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-count-of-positive-integer-and-negative-integer](https://leetcode.cn/problems/maximum-count-of-positive-integer-and-negative-integer/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[-2,-1,-1,1,2,3]', '[-3,-2,-1,0,0,1,2]', '[5,20,66,1314]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCount(self, nums: List[int]) -> int:\n",
    "        sz = len(nums)\n",
    "        nnegative = bisect.bisect_left(nums, 0)\n",
    "        npositive = sz - bisect.bisect_right(nums, 0)\n",
    "        result = max(nnegative, npositive)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCount(self, nums: List[int]) -> int:\n",
    "        return max(sum(i < 0 for i in nums), sum(i > 0 for i in nums))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCount(self, nums: List[int]) -> int:\n",
    "        pos = neg = 0\n",
    "        for num in nums:\n",
    "            if num > 0:\n",
    "                pos += 1\n",
    "            elif num < 0:\n",
    "                neg += 1\n",
    "        return max(pos, neg)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCount(self, nums: List[int]) -> int:\n",
    "        l, r = bisect_left(nums, 0), bisect_right(nums, 0)\n",
    "        return max(l, len(nums) - r)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCount(self, nums: List[int]) -> int:\n",
    "        pos, neg = 0, 0\n",
    "        n = len(nums)\n",
    "\n",
    "        def lower_bound(check) -> int:\n",
    "            left, right = 0, n - 1\n",
    "            while left < right:\n",
    "                mid = left + (right - left) // 2\n",
    "                if check(mid):\n",
    "                    right = mid\n",
    "                else:\n",
    "                    left = mid + 1\n",
    "            \n",
    "            return left if check(left) else n\n",
    "\n",
    "        def upper_bound(check) -> int:\n",
    "            left, right = 0, n - 1\n",
    "            while left < right:\n",
    "                mid = left + (right - left + 1) // 2\n",
    "                if check(mid):\n",
    "                    left = mid\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "            \n",
    "            return left if check(left) else n\n",
    "\n",
    "        pos = n - lower_bound(lambda mid : nums[mid] > 0)\n",
    "        # print('pos = ', pos)\n",
    "        neg = upper_bound(lambda mid : nums[mid]<0) + 1\n",
    "        neg = 0 if neg > n else neg\n",
    "        # print('neg = ', neg)\n",
    "        return max(pos, neg)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List, Tuple, Optional\n",
    "from collections import defaultdict, Counter\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "MOD = int(1e9 + 7)\n",
    "INF = int(1e20)\n",
    "\n",
    "# 给你一个按 非递减顺序 排列的数组 nums ，返回正整数数目和负整数数目中的最大值。\n",
    "\n",
    "# 换句话讲，如果 nums 中正整数的数目是 pos ，而负整数的数目是 neg ，返回 pos 和 neg二者中的最大值。\n",
    "# 注意：0 既不是正整数也不是负整数。\n",
    "class Solution:\n",
    "    def maximumCount(self, nums: List[int]) -> int:\n",
    "        pos = sum(1 for i in nums if i > 0)\n",
    "        neg = sum(1 for i in nums if i < 0)\n",
    "        return max(pos, neg)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCount(self, nums: List[int]) -> int:\n",
    "        pos,neg = 0,0\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] < 0: neg += 1\n",
    "            elif nums[i] > 0: pos += 1\n",
    "        return max(neg,pos)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCount(self, nums: List[int]) -> int:\n",
    "        max_neg = 0\n",
    "        max_pos = 0\n",
    "\n",
    "        for num in nums:\n",
    "            if num < 0:\n",
    "                max_neg += 1\n",
    "            elif num > 0:\n",
    "                max_pos += 1\n",
    "        return max(max_neg, max_pos)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCount(self, nums: List[int]) -> int:\n",
    "\n",
    "        return max(sum(i < 0 for i in nums), sum(i > 0 for i in nums))"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
